package com.leetcode.www;
import java.util.*;
/**
 * Creared with IntelliJ IDEA.
 * Description:给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <=i < len(arr) / 2，都有 arr[2 * i + 1] = 2 * arr[2 * i]”时，返回 true；否则，返回 false。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/array-of-doubled-pairs
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * User:yxd
 * Date:2022-04-02
 * Time:11:25
 */
public class Map954 {
    public boolean canReorderDoubled(int[] arr) {
        if(arr == null && arr.length == 0)return false;
        //List<Integer> list = new ArrayList<>();//存在的意义是为了能保证arr[2 * i + 1] = 2 * arr[2 * i],如果后面需要输出这个数组的话就可以加上这个
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < arr.length;i ++){
            if(!map.containsKey(arr[i])){
                map.put(arr[i],1);
            }else{
                map.put(arr[i],map.get(arr[i]) + 1);
            }
        }
        Arrays.sort(arr);//排序之后保证从最小的数开始匹配2倍值
        for(int i = 0;i < arr.length;i ++){
            if(map.containsKey(arr[i])){
                if(map.containsKey(arr[i] * 2)){//如果都存在那么就删除掉这两个符合条件的值
                   /*list.add(arr[i]);
                    list.add(arr[i] * 2); 可以不需要这个数组*/
                    if(map.get(arr[i]) > 1){
                        map.put(arr[i],map.get(arr[i]) - 1);
                    }else{
                        map.remove(arr[i]);
                    }
                    if(map.containsKey(arr[i] * 2)){//如果是0的话,就需要再看一下还有没有0了
                        if(map.get(arr[i] * 2) > 1){
                            map.put(arr[i] * 2,map.get(arr[i] * 2) - 1);
                        }else{
                            map.remove(arr[i] * 2);
                        }
                    }else{
                        return false;
                    }

                }
            }
        }
        return map.size() == 0;//看最后map里面的元素使用完了没有
    }
}
